The modern intelligent telephone network is essentially composed of three functional elements. These are service switching points (SSPs), signalling transfer points (STPs), and service control points (SCPs). When a telephone user attempts to make a telephone call, the SSP is the first network element with which the user interacts. The SSP is a system that provides part of the intelligence in the intelligent network. It receives information from the user and determines if some form of special handling is required. For example, if the user had dialed an 800 number, the SSP, upon recognizing the 800 number, would know it would require detailed information for processing the call. The SSP would then send a query message through the company's signalling network to a service control point (SCP) to obtain the call processing information. The service control point (SCP) would process the query message and search its database for the customer record identified by the 800 number in the query message. The SCP would extract the necessary call processing information from the customer record in the database and package this information in a response message to be sent back through the signalling network to the SSP that sent the initial query.
The SCP as the service controller sits at the top of the intelligent network topology. Within a telephone region there may be one SCP pair (the pair is for reliability purposes) that is accessed by a pair of regional signalling transfer points (STPs) which in turn have access to several pairs of local signalling transfer points (STPs). Therefore, between each SCP pair and the paired set of STPs directly connected to it are two signalling linksets. Each signalling linkset consists of multiple (1 to 15) links. In the art, one linkset between an SCP and one of STPs in the paired set is call Linkset-0. The other linkset between the SCP and the other STP of the paired set is known in the art as Linkset-1.
At the bottom of the network topology connected to the local STPs are a wide plurality of service switching points (SSPs) which provide the direct contact to the telephone customers in providing telephone services. With one SCP pair supporting such a wide number of STPs and SSPs, and as more advanced and customized services are provided by the telephone service providers, the volume of message requests received at the SCP is becoming very large. Consequently, the SCP has taken on critical importance as the "real brains" in the intelligent network. Furthermore, because the multiple sources of the messages are all initiated independently by customers when they request service, the message traffic at the SCP arrives according to random processes. It is therefore important that the message processing performance of an SCP meet strict long term performance standards and also that the SCP be able to avoid or alleviate congestion in its handling peak message traffic loads that undoubtedly and periodically occur.
Bell Communications Research Inc. (Bellcore) has developed an SCP architecture and software that has been deployed and used to great success in the telephone operations of many telephone companies including the Regional Bell Operating Companies. The current standard configuration of Bellcore's SCP includes eight front ends (FEs) that connect and interface the SCP with the common channel signalling network (i.e. the STPs) and three (3) to five (5) Control Processors (CPs) which process database queries as required to provide the 800 and Alternate Billing Services. Each of the front end processors has links to both linksets (Linkset-0 and Linkset-1) connecting the SCP to the STPs. Having multiple front end processors and control processors operating independently is necessary to assure overall reliability and response time performance of the SCP in providing high quality telephone services.
In the current SCP architecture, one of the problems that had to be addressed was the routing of outgoing messages to multiple front end processors from multiple independent control processors and the distribution of the traffic among the front end processors when the query messages arrive at the control processors according to a random process. The current method for routing the outgoing messages from each of the independent control processors has been to use a stochastic rule to distribute message traffic among the front end processors.
Simply stated, the prior art stochastic method of distributing traffic to all the front end processors is to have each control processor, using a random number generator, route each message to a front end processor based on the random number generated. With this approach, each control processor operates independently, routing its own traffic randomly to each of the front end processors.
Experience, however, has shown that although the stochastic rule will equally distribute the traffic load across the front end processors over long time periods, load imbalances over short periods of time, to the point of causing congestion and thereby discarding messages, have been observed. The following example illustrates this point. Let us assume an SCP has 8 Front End processors (FEs) and 5 Control Processors (CPs). Further assume that an FE goes into congestion if it has to handle more than 65 queries (or messages) per second, while the CP can handle about 100 queries per second. Also assume that incoming traffic is Poisson distributed and is arriving at a Poisson mean rate of 450 queries per second. Using the prior art stochastic algorithm to route the traffic, it is possible that all 5 CPs could send a buffer of 12 messages to a given FE at the same time. Furthermore, after this FE receives all 5 buffers, it is possible that one of the CP's could send another full buffer of 12 messages to the same FE. For an SCP in the Signalling System 7 (SS7) network, the probability of an FE receiving 5 buffers (one from each CP) and then receiving another buffer from one CP in quick succession (e.g. within 10-15 milliseconds) is about 1.12.times.10.sup.-5 When this happens, the FE needs to handle 72 messages in a very short time. Since it is only able to handle 65 queries per second, it will experience transmit congestion and start discarding messages until congestion abates. At the incoming traffic rate of 450 queries per second, we estimate that one of the 8 FEs will experience congestion about every 25 minutes. For other SCP configurations, congestion may occur more frequently. For example, in a configuration with 6 FEs and 4 CPs, at a traffic arrival rate of 300 queries per second, congestion is expected, and in practice was observed, about every 3 to 5 minutes. Therefore, it is an object of our invention to control the message traffic load at the front end processors so as to eliminate short term load imbalances.
In the prior art, other routing methods have been examined. For example, Tak-Shing P. Yum in his paper entitled "The Design and Analysis of a Semidynamic Deterministic Routing Rule", published in IEEE Transactions on Communications, Vol. 29, No. 4, April 1981, examines a best deterministic rule for minimizing waiting times in a common channel signalling network. The best deterministic rule disclosed by Mr. Yum is one where instead of distributing the traffic to different queues randomly, it is distributed according to a calculable routing sequence. Mr. Yum showed that this best deterministic rule can maintain equal utilization of signalling links in the network while reducing average waiting times. However, Mr. Yum's method processes individual messages, while current SCPs process blocks containing a variable number of messages. A direct application of Mr. Yum's algorithm to the SCP at the block level would result in a traffic imbalance among the FEs. The differences in the number of messages per block at the front end processors further compound the problem of trying to maintain the load balance (i.e. processing load) across the front end processors. It is therefore a further object of our invention to incorporate into a deterministic method for routing traffic in an SCP the need to accommodate variability in the number of messages per block on equalizing the processing load of the front end processors.